1. Field of the Invention
The present invention relates to multiprocessor computer systems and, more specifically, to a directory for maintaining status information over data stored in a multiprocessor computer system.
2. Background Information
A computer system typically comprises one or more processors linked to a main memory by a bus or other interconnect. In most computer systems, main memory organizes the instructions and data being stored into units typically referred to as “blocks”, each of which is separately addressable and may be of a fixed size. Instructions and data are typically moved about the computer system in terms of one or more blocks.
Ordinarily, a processor will retrieve data, e.g., one or more blocks, from main memory, perform some operation on it, and eventually return the results back to main memory. Retrieving data from main memory and providing it to a processor can take significant time especially in terms of the high operating speeds of processors. To reduce such latencies as well as to reduce the number of times a processor must access main memory, modern processors and/or processor chipsets include one or more cache memories or caches. A cache is a small, fast memory module that is placed in close proximity to the processor. Many caches are static random access memories (SRAMs), which are faster, but more expensive, than dynamic random access memories (DRAMs), which are often used for main memory. The cache is used to store information, e.g., data or instructions, which the processor is currently using or is likely to use in the near future. There are two basic types of caches: “write-through” caches and “write-back” caches.
With a write-through cache, whenever a processor modifies or updates a piece of data in the processor's cache, main memory's copy of that data is automatically updated. This is accomplished by having the processor write the data back to memory whenever the data is modified or updated. Utilization of a write-through cache means that main memory always has the most up-to-date version of data. Nonetheless, a write-through cache forces the processor to constantly interrupt its current task or thread in order to write data back to memory as soon as it is modified. The write-through cache may also impose significant burdens on the processor to memory interconnect, degrading system performance.
A write-back cache, in contrast, does not automatically send modified or updated data to main memory. Instead, the updated data remains in the cache until some more convenient time, e.g., when the processor is idle, at which point the modified data is written back to memory. The utilization of write-back caches typically improves system performance. In some systems, a write-back or victim buffer is provided in addition to the cache. Victim data refers to modified data that is being removed from the processor's cache in order to make room for new data received at the processor. Typically, the data selected for removal from the cache is data the processor is no longer using. The victim buffer stores this modified data which is waiting to be written back to main memory. The use of a victim buffer frees up space in the cache for data that is being used or will be used by the processor. Modified data in the victim buffer is eventually “victimized”, i.e., written back to main memory, at some convenient time.
Although the implementation of write-back or victim buffers have increased the performance of computer systems, there are some drawbacks. For example, the addition of a victim buffer requires additional storage or memory space at the processor chipset increasing cost, complexity and size of the processor chipset.
Symmetrical Multiprocessor (SMP) Systems
Multiprocessor computing systems, such as symmetrical multiprocessor (SMP) systems, provide a computer environment in which software applications may run on a plurality of processors using a single address space or shared memory abstraction. In a shared memory system, each processor can access any data item without a programmer having to worry about where the data is or how to obtain its value. This frees the programmer to focus on program development rather than on managing partitioned data sets and communicating values.
Cache Coherency
Because more than one processor of the SMP system may request a copy of the same memory block from main memory, cache coherency protocols have been developed to ensure that no processor relies on a memory block that has become stale, typically due to a modification or update performed to the block by some other processor. Many cache coherency protocols associate a state with each cache line. A given memory block, for example, may be in a shared state in which copies of the block may be present in the caches associated with multiple processors. When a memory block is in the shared state, a processor may read from, but not write to, the respective block. To support write operations, a memory block may be in an exclusive state. In this case, the block is owned by a single processor which may write to the cache line. When the processor updates or modifies the block, its copy becomes the most up-to-date version, while corresponding copies of the memory block at main memory and/or other processor caches become stale.
When a processor wishes to obtain exclusive ownership over a memory block that is currently in the shared state (i.e., copies of the block are present in the caches of other processors), invalidate requests are typically issued to those other processors. When an invalidate request is received by a given processor, its cache is searched for the specified memory block. If the specified block is found, it is transitioned to an invalid state. Many caches assign or associate a valid bit with each memory block or cache line stored in the cache. If the bit is asserted, then the cache line is considered to be valid and may be accessed and utilized by the processor. When a memory block is initially received from main memory, the valid bit is typically asserted and the memory block is stored in the cache. When an invalidate request is received, the valid bit of the respective cache line is de-asserted, thereby indicating that the cache line is no longer valid.
There are two classes of cache coherency protocols: snooping and directory based. With snooping, the caches monitor or snoop all transactions traversing the shared memory bus, looking for those transactions that reference a memory block stored at the cache. If such a transaction is detected, the cache updates the status information for its copy of the memory block. In this way, every cache that has a copy of a given memory block also has a copy of the status information of that block. With a directory based protocol, the sharing status of all blocks is kept in a single, centralized location in the system, called a directory. Sharing status is not maintained in the individual caches.
FIG. 1 is a highly schematic illustration of a prior art directory 100. Directory 100 has a plurality of entries 102a–d each of which corresponds to a respective memory block. The directory 100 is organized, moreover, such that each entry 102a–d has a plurality of fields or cells for storing state and/or status information for the respective block. In particular, the directory 100 has an address column 103 that stores the address of the memory block, an owner column 104 that stores the identity of the entity, e.g., a processor or main memory itself, that is considered to be the owner of the memory block, and a sharer column 106 that stores the identity of those processors or other system entities that have a shared copy of the block.
The sharer column 106 may have a plurality of sub-columns 106a–c, each of which may contain the identity of a particular processor that has a shared copy of the respective memory block. If a request for shared access to a memory block is received from a first processor, P1, main memory examines the directory entry, e.g., entry 102c, for the block to determine its owner. As memory is itself the owner of the block, memory sends its copy of the block to P1 and enters P1's identifier (ID) into one of the sharer fields, e.g. field 106b, of the respective directory entry, e.g., entry 102c, thereby noting that P1 has a shared copy of the block. Since P1 only requested shared access to the memory block, the contents of the entry's owner field 104 are not modified.
If P1 issues a request for exclusive or write access to some other memory block, e.g., the block corresponding to entry 102d, main memory again examines the contents of entry 102d. Suppose that, at the time the request is received, the owner field reflected that memory was the owner of the memory block as shown in parentheses. In this case, memory sends the block to P1, and replaces the contents of the owner field 104 with P1's ID to reflect that P1, rather than memory, is now the owner of the memory block. P1 may then modify or update the memory block. If a request from a second processor, P2, is subsequently received for a shared copy of this memory block, main memory examines entry 102d of the directory 100 and determines that P1 is the owner of the memory block. Because its copy of the memory block, i.e., the copy stored at memory, may be stale, memory does not forward its copy to P2. Instead, memory may be configured to forward the request to P1 and add P2's ID to one of the sharer fields, e.g., field 106a. In response to the forwarded request, P1 may then supply P2 with a copy of the modified memory block from P1's cache. Alternatively, memory may be configured to force P1 to relinquish ownership of the memory block and return the modified version to memory so that memory can send a copy of the up-to-date version to P2.
It has been recognized that a computer system's cache coherency protocol is a key factor in the system's ultimate performance. Poorly designed cache coherency protocols can result in latencies, bottlenecks, other inefficiencies and/or higher complexity, each of which may reduce performance and/or increase cost. Bottlenecks, for example, often arise in high occupancy controllers, such as directory controllers. “Occupancy” is a term of art and refers to the amount of time a controller is unavailable, e.g., for the servicing of requests, following receipt of an earlier request.
In some cache coherency protocols, when a directory controller receives a request corresponding to a memory block, it thereafter becomes unavailable to service other requests for that memory block until certain acknowledgements to the earlier request are received back at the directory controller. The resulting delays can adversely affect system performance. In response, efforts have been made to design low occupancy cache coherency protocols. A low occupancy protocol allows multiple requests to the same memory block to be executing substantially simultaneously within the computer system. U.S. Pat. No. 6,154,816, issued Nov. 28, 2000, for a LOW OCCUPANCY PROTOCOL FOR MANAGING CONCURRENT TRANSACTIONS WITH DEPENDENCIES, which is commonly owned with the present invention, describes a low occupancy cache coherency protocol.
Read-Modify-Write
As described above, when an owner processor, such as P1 is finished with a memory block that it modified, the processor writes the modified memory block back to main memory. To write-back data from its write-back or victim buffer, the processor typically performs an atomic read-modify-write operation. Suppose, for example, that P1 is writing back to memory the modified memory block corresponding to directory entry 102d. P1 first reads the contents of the owner field 104 for entry 102d and compares this value to its own ID. If the value read from the owner field 104 matches P1's ID, then P1 can proceed with the write-back. Next, P1 modifies the owner field 104 of entry 102d by entering the ID associated with memory into this field. P1 then writes the modified memory block back into memory. By updating the owner field 104 with the ID assigned to main memory, P1 ensures that memory will now consider itself to be the owner of the cache line. Subsequent requests for copies of the memory block can thus be serviced by memory as it now has the most up-to-date version of the cache line.
If, during the write-back operation, P1 determines that the value stored at the owner field 104 does not match P1's ID, then P1 concludes that some entity other than P1 has somehow become the owner of the memory block. In this case, P1's copy of the cache line may no longer be the most up-to-date version. Accordingly, P1 aborts the write-back operation and neither updates the owner field 104 nor writes its copy of the data back to memory.
As shown, the utilization of an atomic read-modify-write operation to execute a write-back ensures that the status information in the directory is correct. However, the need to perform an atomic read-modify-write operation for every write-back results in the consumption of significant bandwidth on the bus connecting the processor to the main memory. Accordingly, a need exists for performing write-backs from a processor cache to main memory in a more efficient manner.